package com.chenken;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉搜索树 Binary Search Tree 简称BST  ,又称为二叉查找树，二叉排序树
 * 特性：
 * 左子节点的所有元素都要比它的父节点要小
 * 右子节点的所有 元素都要比它的父节点要大
 * 它的左右子树也是一颗二叉搜索树
 * 二叉搜索树可以大大提高数据搜索的效率
 * 它的元素必须具有可比较性，元素不允许为null
 * 它没有索引
 */
public abstract class BinarySearchTree<E> extends BinaryTree<E>{

	/**
	 * 比较器
	 */
	private Comparator<E> comparator;
	
	public BinarySearchTree() {
		this(null);
	}
	
	public BinarySearchTree(Comparator<E> comparator) {
		this.comparator = comparator;
	}
	
	public void add(E element){
		elementNotNullCheck(element);
		//	如果根节点不存在，该元素为根节点
		if(root == null) {
			root = createNewNode(element, null);
			size++;
			afterAdd(root);
			return;
		}
		//	找到父节点
		Node<E> node = root;
		Node<E> parent = root;
		int cmp = 0;
		while (node!=null) {
			cmp = compare(element, node.element);
			parent = node;
			if(cmp > 0) {
				node = node.right;
			}else if(cmp < 0) {
				node = node.left;
			}else {
				node.element = element;
				return;
			}
		}
		//	看看插入到父节点的左还是右
		Node<E> newNode = createNewNode(element, parent);
		if(cmp > 0) {
			parent.right = newNode;
		}else {
			parent.left = newNode;
		}
		afterAdd(newNode);
		size++;
	}
	
	protected abstract void afterAdd(Node<E> node);
	
	protected abstract void afterRemove(Node<E> node);
	
	
	@SuppressWarnings("unchecked")
	private int compare(E e1,E e2) {
		//	如果传了比较器，就按照比较器的逻辑来比
		if(comparator != null) {
			return comparator.compare(e1, e2);
		}
		//	如果没传比较器，由于二叉搜索树的所有元素必须具有可比较性，这里强转e1为Comparable类型
		return ((Comparable<E>)e1).compareTo(e2);
	}
	
	public void remove(E element) {
		if(element == null) {
			return;
		}
		if(compare(root.element, element) == 0) {
			remove(root);
		} else{
			Node<E> node = node(element);
			if(node != null) {
				remove(node);
			}
		}
	}
	
	/**
	 * 根据element找到节点
	 * @param element
	 * @return
	 */
	private Node<E> node(E element){
		Node<E> node = root;
		while(node != null) {
			int comp = compare(node.element,element);
			if(comp == 0) {
				return node;
			}
			if(comp > 0) {
				node = node.left;
			}else{
				node = node.right;
			}
		}
		return node;
	}
	
	private void remove(Node<E> node) {
		size--;
		//node是度为2的节点
		if(node.hasTwoChildren()) {
			Node<E> successor = successor(node);//找到后继节点
			node.element = successor.element;//将值替换
			node = successor;	//将node指向successor
		}
		//node是叶子节点
		if(node.isLeaf()) {
			removeLeaf(node);
			afterRemove(node);
			return;
		}
		//node是度为1的节点
		if(node.hasOneChild()) {
			removeOneChildNode(node);
			afterRemove(node);
			return;
		}
	}
	
	/**
	 * 删除叶子节点
	 * @param node
	 */
	private void removeLeaf(Node<E> node) {
		if(node.parent == null) {
			root = null;
		}else {
			if(node.parent.left == node) {
				node.parent.left = null;
			}else {
				node.parent.right = null;
			}
		}
	}
	/**
	 * 删除度为1的节点
	 * @param node
	 */
	private void removeOneChildNode(Node<E> node) {
		Node<E> replacement = node.left !=null ?node.left:node.right;
		replacement.parent = node.parent;
		if(node.parent == null) {	//node是度为1的根节点
			root = replacement;
		}else if(node.parent.left == node) {
			node.parent.left = replacement;
		}else {
			node.parent.right = replacement;
		}
	}
	
	/**
	 * 是否包含元素
	 * @param element
	 * @return
	 */
	public boolean contain(E element) {
		return node(element) != null;
	}
	
	private void elementNotNullCheck(E element) {
		if(element == null) {
			throw new IllegalArgumentException("element must not be null");
		}
	}
	
	/**
	 * 前序遍历
	 */
	public void preorderTraversal() {
		System.out.println("前序遍历");
		preorderTraversal(root);
	}
	
	private void preorderTraversal(Node<E> node) {
		if(node == null) {
			return;
		}
		System.out.println(node.element);
		preorderTraversal(node.left);
		preorderTraversal(node.right);
	}
	
	/**
	 * 中序遍历
	 */
	public void inorderTraversal() {
		System.out.println("中序遍历");
		inorderTraversal(root);
	}
	
	private void inorderTraversal(Node<E> node) {
		if(node == null) {
			return;
		}
		inorderTraversal(node.left);
		System.out.println(node.element);
		inorderTraversal(node.right);
	}
	
	/**
	 * 后序遍历
	 */
	public void postinorderTraversal(Visitor<E> visitor) {
		System.out.println("后序遍历");
		postinorderTraversal(root,visitor);
	}
	
	private void postinorderTraversal(Node<E> node,Visitor<E> visitor) {
		if(node == null) {
			return;
		}
		inorderTraversal(node.left);
		inorderTraversal(node.right);
		System.out.println(node.element);
	}
	
	/**
	 * 层序遍历
	*/
	public void levelOrderTraversal(Visitor<E> visitor) {
		System.out.println("层序遍历");
		if(root == null || visitor == null) {
			return;
		}
		Queue<Node<E>> queue = new LinkedList<Node<E>>();
		queue.offer(root);//将根节点入队
		while(!queue.isEmpty()) {
			Node<E> node = queue.poll();//将队头出队
			if(visitor.visit(node.element)) {	//	访问
				return;
			} 
			if(node.left!=null) {
				queue.offer(node.left);//将左子节点入队
			}
			if(node.right!=null) {
				queue.offer(node.right);//将右子节点入队
			}
		}
	}
	
	public static interface Visitor<E>{
		boolean visit(E element);
	}

}
